package LeetCodeHot100TopInterview;

//岛屿数量
//并查集 || 暴力尝试 [[先 用暴力递归 此题的暴力递归性能贼好
//给你一个由 '1'（陆地）和 '0'（水）组成的的二维网格，请你计算网格中岛屿的数量

public class Q200_IslandNum {
    //暴力递归加剪枝可以达到一个很好的性能
    //每个点遍历一遍 上下左右四个方向 但是有剪枝行为 复杂度 O(N * M) M = 4 (每个点被来自周围的访问)
    public int numIslands(char[][] grid) {
        if (grid == null || grid.length == 0){
            return 0;
        }
        //每个点遍历一遍
        int ans = 0;
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[0].length; j++) {
                if (grid[i][j] == '1'){
                    //有1就必有岛屿
                    ans ++;
                    //这一步是一个感染过程
                    process(grid, i, j);
                }
            }
        }
        return ans;

    }

    public void process(char[][] grid, int row, int col){

        if (row == -1 || row == grid.length || col == -1 || col == grid[0].length
                || grid[row][col] == '2' || grid[row][col] == '0'){ //剪枝
            return;
        }
        //做一个感染
        if (grid[row][col] =='1'){
            grid[row][col] = '2';
        }

        //上
        process(grid, row - 1, col);
        //下
        process(grid, row + 1, col);
        //左
        process(grid, row, col - 1);
        //右
        process(grid, row , col + 1);

    }

    public static void main(String[] args) {
//        Q200_IslandNum fun = new Q200_IslandNum();
//        fun.numIslands(new char[][]{
//                {}
//        })
    }
}
